
//438.找到字符串中所有字母异味词
class Solution {
    public:
        vector<int> findAnagrams(string s2, string s1) {
            int k=s1.size(),n=s2.size();
            if(k>n) return {};  //s1的长度小于s2，必定没有满足条件的
            //通过一个长度为k的滑动窗口来实现,需要对s1的字符种类及个数进行计数来决定其是否是子串
            int ch[26]={0};   //通过ch来记录s1字符的种类及个数
            int num=0;      //用num来记录s1有多少个不同的字符，方便判断s2的区间中是否是字串
    
            for(auto e:s1) 
            {
                if(ch[e-'a']==0) num++;
                ch[e-'a']++;
            }
            int left=0,right=0;
            vector<int> ret;
            while(right<n)
            {
                //入窗口
                while(right<n&&right-left<k)
                {
                    ch[s2[right]-'a']--;
                    if(ch[s2[right]-'a']==0) num--;
                    if(num==0) ret.push_back(left);    //此时区间内所有的字符都能在s1中找到，将第一个位置的下标插入
                    right++;
                }
    
                //出窗口
                if(ch[s2[left]-'a']==0) num++;
                ch[s2[left]-'a']++;
                left++;
            }
            return ret;
    
        }
    };